// 双重循环
function trap(height) {
  let result = 0
  for (let i = 0; i < height.length - 1; i++) {
    let leftMax = 0, rightMax = 0
    for (let j = 0; j <= i; j++) {
      leftMax = Math.max(leftMax, height[j])
    }
    for (let k = i; k < height.length; k++) {
      rightMax = Math.max(rightMax, height[k])
    }
    result += Math.min(leftMax, rightMax) - height[i]
  }
  return result
}

// 单调递减栈
function trap(height) {
  let res = 0, stack = []
  for (let i = 0; i < height.length; i++) {
    while (stack.length !== 0 && height[stack[stack.length - 1]] < height[i]) {
      let bottomIdx = stack.pop()
      while (stack.length !== 0 && height[stack[stack.length - 1]] < height[bottomIdx]) {
        stack.pop()
      }
      if (stack.length !== 0) {
        let width = i - stack[stack.length - 1] - 1
        res += (Math.min(height[stack[stack.length - 1]], height[i]) - height[bottomIdx]) * width
      }
    }
    stack.push(i)
  }
  return res
}